home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_2 / qsort < prev    next >
Text File  |  1995-03-31  |  4KB  |  91 lines
  1. Article 1643 of comp.sys.handhelds:
  2. From: alonzo@microsoft.UUCP (Alonzo GARIEPY)
  3. Newsgroups: comp.sys.handhelds
  4. Subject: More quicksort
  5. Date: 27 Mar 90 23:03:27 GMT
  6. Organization: Microsoft Corp., Redmond WA
  7.  
  8. Here is yet another incarnation of quicksort for the HP 48.
  9.  
  10. This variation differs in that only one copy of each element
  11. exists while the sort is taking place.  All objects are kept 
  12. on the stack (as references) so that the memory overhead is 
  13. about 5 nibbles per element (2500 bytes for a 1000 element
  14. list).  This is most helpful when you are sorting large objects
  15. or are low on memory.
  16.  
  17. It is possible to use less memory by sorting in place, but that
  18. would be extremely slow because of list handling.  Sorting with 
  19. an array of references is a typical way to avoid the cost of
  20. copying data during a sort.
  21.  
  22. In one test, this sort took about 24 minutes for a list of 500 
  23. random real number.  It could be made faster by eliminating one 
  24. or both of the temporary variables.   The sort could be made
  25. faster by replacing the code, 1 i START n ROLLD NEXT, with a
  26. single machine code command.  I'll see what I can do.
  27.  
  28. QSORT
  29. %%HP: T(3)A(D)F(.);
  30. \<< LIST\-> QST \->LIST \>>    @ sorts a list on the stack @
  31.  
  32. QST
  33. %%HP: T(3)A(D)F(.);
  34. \<< \-> n            @ sorts a disassembled list on the stack @
  35.     \<< n 2 / ROLL n 3 + 2 n
  36.         START ROT 3 DUPN SWAP ROLLD > - NEXT 
  37.     4 - \-> i 
  38.     \<< n ROLLD 
  39.             i IF DUP 1 > THEN QST END
  40.             IF DUP THEN 1 SWAP START n ROLLD NEXT i END 
  41.             n SWAP 1 + - IF DUP 1 > THEN QST END DROP n
  42. \>> \>> \>>
  43.  
  44. Sedgewick has shown that by quicksorting only until no sublist contains
  45. greater than X elements (where X is 10 to 20) and then doing an insertion
  46. sort on the resultant almost-sorted list, it is possible to get up to 20%
  47. improvement in speed.  Mark Adler brought this to my attention.  
  48.  
  49. You can do that by changing the two instances of "1 >" in QST to "X >".
  50. Then you need to perform an insertion sort on the partly sorted result of
  51. QSORT.  Since I haven't come up with a decent selection or insertion sort, 
  52. I prefer to leave the resolution at 1 and take my lumps.  I invite others
  53. to make these improvements.
  54.  
  55. The main speed considerations in sorting on the HP 28/48 are two.
  56.  
  57. 1.  It is much faster to manipulate objects on the stack than to use 
  58.     lists.  Moving stack objects is just a question of switching five 
  59.     nibble pointers, but moving elements in a list involves copying
  60.     the objects themselves with all the requisite memory managment.
  61.  
  62. 2.  It is much faster to manipulate objects within global variables
  63.     than those in the heap.  Each entry in the stack is a pointer to
  64.     an object.  If the object was put on the stack by recalling or
  65.     disassembling (GET, GETI, OBJ->, LIST->, etc.) a global variable,
  66.     or by duplicating (DUP, OVER, etc.) an object that derives from
  67.     a global variable, it will not be subject to garbage collection.
  68.     Entries that result from calculation (PUT, ->LIST, +, SUB, etc.)
  69.     point to objects in the heap and must be garbage collected.
  70.  
  71. The program above will sort a list of 500 random numbers in 4 minutes
  72. and 21 seconds(1).  A list of 1000 random numbers took about 10 minutes
  73. and 35 seconds(2).  If you want to make sure you get this behaviour for
  74. lists on the stack that may not derive from global variables, you can 
  75. modify QSORT to stash them in a temporary variable during the sort.
  76.  
  77. GQSORT
  78. %%HP: T(3)A(D)F(.);
  79. \<< 'QQQ' DUP PURGE STO QQQ LIST\-> QST 'QQQ' PURGE \->LIST \>>
  80.  
  81. Do not use GQSORT for big lists that are already in global variables
  82. because storing a second copy in QQQ will make the sort slower.
  83.  
  84. Alonzo Gariepy
  85. alonzo@microsoft
  86.  
  87. (1) On an HP 48 with 17 Kb of free memory (not including the list).
  88. (2) On an HP 48 with 50 Kb of free memory (not including the list).
  89.  
  90.  
  91.